//
// Description: 45. 跳跃游戏II
// Created by Loading on 2021/4/3.
//

#include <bits/stdc++.h>

using namespace std;

//贪心算法
int jump(vector<int> &nums) {
    //可以到达的最远距离
    //每个元素可以到达的最远距离为：nums[i] + i
    int far_most = 0;
    //当前可以到达的边界
    int current_end = 0;
    //最少的步数
    int min_op = 0;
    //放弃遍历最后一个元素，因为会增加不必要的一步
    for (int i = 0; i < nums.size() - 1; ++i) {
        //更新可以到达的最远距离
        far_most = max(far_most, nums[i] + i);

        if (far_most >= nums.size() - 1) {//已经可以到达
            return min_op + 1;
        } else {//还不可以到达，如果到当前可以到达的边界，步数+1，更新当前可以到达的边界值
            if (i == current_end) {
                min_op++;
                current_end = far_most;
            }
        }
    }

    return min_op;
}

int main() {
    vector<int> nums = {3, 2, 100, 1, 1, 1, 4};
    cout << jump(nums) << endl;
}